package 笔试;

import java.util.Arrays;

public class CarTest {
    int pathValue = 0;
    int pathSize = 0;
    int resDiff = Integer.MAX_VALUE;
    int resValue = 0;
    int tmp = 0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给出一个数组，在数组中找到两个数，使得它们的和最接近目标值但不超过目标值，返回它们的和
     * @param array int整型一维数组 数组
     * @param target int整型 目标值
     * @return int整型
     */
    public int closestValue (int[] array, int target) {
        // write code here
        Arrays.sort(array);
        if(array[0]+array[1]>target) return -1;
        backtrack(array,target,0);
        return resValue;
    }

    public void backtrack(int[] nums,int target,int index){
        if(pathSize==2){
            tmp = Math.abs(pathValue-target);
            if(resDiff>tmp){
                resDiff = tmp;
                resValue = pathValue;
            }
            return;
        }
        for(int i=index;i<nums.length;i++){
            pathValue = pathValue+nums[i];
            pathSize++;
            backtrack(nums,target,i+1);
            pathSize--;
            pathValue = pathValue-nums[i];
        }
    }
}
